package leetcode.editor.cn;

//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 示例 4： 
//
// 
//输入：s = "([)]"
//输出：false
// 
//
// 示例 5： 
//
// 
//输入：s = "{[]}"
//输出：true 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 仅由括号 '()[]{}' 组成 
// 
// Related Topics 栈 字符串 
// 👍 2335 👎 0

import java.util.Stack;

public class ValidParentheses{
    public static void main(String[] args) {
        Solution solution = new ValidParentheses().new Solution(); 
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c =='('){
                stack.push(')');
            } else if (c=='['){
                stack.push(']');
            } else if(c=='{'){
                stack.push('}');
            }

            /*消除问题：如果下一位和栈顶的元素相同，则表示配对正确，弹出该元素，进入下一位；
            * 如果不同，则直接返回false.*/
            //因为配对正确的情况下，先进栈的肯定是左括号，
            //如果直接进右括号，则可以直接报错。
            else if(stack.isEmpty()||c!=stack.pop()){
                return false;
            }
        }
        //当全部配对正确时，stack中应该为空。
        return stack.isEmpty();

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}